//#define _CRT_SECURE_NO_WARNINGS
//
//#include "ALL.h"
//
//TreeNode* BuyTreeNode(DataType x)
//{
//	TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
//	assert(newnode);
//	newnode->data = x;
//	newnode->left = NULL;
//	newnode->right = NULL;
//
//	return newnode;
//}
//
//TreeNode* BuyTree()
//{
//	TreeNode* n1 = BuyTreeNode(1);
//	TreeNode* n2 = BuyTreeNode(2);
//	TreeNode* n3 = BuyTreeNode(3);
//	TreeNode* n4 = BuyTreeNode(4);
//	TreeNode* n5 = BuyTreeNode(5);
//	TreeNode* n6 = BuyTreeNode(6);
//
//	n1->left = n2;
//	n2->left = n3;
//	n1->right = n4;
//	n4->left = n5;
//	n4->right = n6;
//
//	return n1;
//}
//
//void PreOrder(TreeNode* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL ");
//		return;
//	}
//
//	printf("%d ", root->data);
//	PreOrder(root->left);
//	PreOrder(root->right);
//}
//
//void InOrder(TreeNode* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL ");
//		return;
//	}
//
//	InOrder(root->left);
//	printf("%d ", root->data);
//	InOrder(root->right);
//}
//
//void PostOrder(TreeNode* root)
//{
//	if (root == NULL)
//	{
//		printf("NULL ");
//		return;
//	}
//
//	PostOrder(root->left);
//	PostOrder(root->right);
//	printf("%d ", root->data);
//}
//
//int TreeNodeSize(TreeNode* root)
//{
//	return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
//}
//
//int TreeLeafSize(TreeNode* root)
//{
//	if (root == NULL) return 0;
//	if (root->left == NULL && root->right == NULL) return 1;
//
//	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
//}
//
//int TreeHeight(TreeNode* root)
//{
//	if (root == NULL) return 0;
//
//	int leftheight = TreeHeight(root->left);
//	int rightheight = TreeHeight(root->right);
//
//	return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
//}
//
//int TreeKLSize(TreeNode* root, int k)
//{
//	if (root == NULL) return 0;
//	if (k == 1) return 1;
//
//	return TreeKLSize(root->left, k - 1) + TreeKLSize(root->right, k - 1);
//}
//
//TreeNode* TreeNodeFind(TreeNode* root, DataType x)
//{
//	if (root == NULL) return NULL;
//
//	if (root->data == x) return root;
//
//	TreeNode* lret = TreeNodeFind(root->left, x);
//	if (lret) return lret;
//
//	TreeNode* rret = TreeNodeFind(root->right, x);
//	if (rret) return rret;
//
//	return NULL;
//}
//
//void LevelOrder(TreeNode* root)
//{
//	Que q;
//	QInit(&q);
//
//	if (root) QPush(&q, root);
//
//	while (!QEmpty(&q))
//	{
//		TreeNode* front = QFront(&q);
//		QPop(&q);
//		printf("%d ", front->data);
//
//		if (front->left) QPush(&q, front->left);
//		if (front->right) QPush(&q, front->right);
//	}
//
//	printf("\n");
//	QDestroy(&q);
//}
//
//bool TreeComplete(TreeNode* root)
//{
//	Que q;
//	QInit(&q);
//
//	if (root) QPush(&q, root);
//
//	while (!QEmpty(&q))
//	{
//		TreeNode* front = QFront(&q);
//		QPop(&q);
//
//		if (front == NULL) break;
//
//		QPush(&q, front->left);
//		QPush(&q, front->right);
//	}
//
//	while (!QEmpty(&q))
//	{
//		TreeNode* front = QFront(&q);
//		QPop(&q);
//
//		if (front)
//		{
//			QDestroy(&q);
//			return false;
//		}
//	}
//
//	QDestroy(&q);
//	return true;
//}
//
//void TreeDestroy(TreeNode* root)
//{
//	if (root == NULL) return;
//
//	TreeDestroy(root->left);
//	TreeDestroy(root->right);
//	free(root);
//}